package com.love.labuladong.greedy;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author : zh
 * @Description : (牛客)BM96 主持人调度（二）
 * 此题就是计算最大重叠部分的个数的问题
 *
 * @Date : 2024-09-19 11:15
 */
public class MinNumberOfHost {

    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // 这里的比较最好写这样的[测试数据会整很大，加减会影响精度]
        // 根据 每组数据的 开始数字 从小到大排序
        Arrays.sort(startEnd,0,n,(a,b) -> Integer.compare(a[0],b[0]));
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> a.compareTo(b) );
        // 第一个单独处理，即使后面一个重叠的都没有，最大的重叠个数也为1
        heap.add(startEnd[0][1]);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            while (!heap.isEmpty() && heap.peek() <= startEnd[i][0]){
                heap.poll();
            }
            heap.add(startEnd[i][1]);
            // 放入一次就记一次答案
            ans = Math.max(ans,heap.size());
        }
        return ans;

    }

}
